
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;

/**
 * A class representing a Sokoban board in a manner suitable for fast AI operations.
 * @author Jan
 */
public class Board {
	
	/** A map of the tiles on which players can walk and/or boxes can be placed. */
	public boolean[][] floor;
	
	/** A map of the tiles on which boxes can be placed without loosing the game. */
	public boolean[][] safeTiles;
	
	
	/** An array containing the coordinates of all targets */
	public Pos[] targets;

	/** The position of the player */
	public Pos player;

	/** A map of the tiles where boxes are placed */
	public boolean[][] boxmap = null;

	/** An array containing the coordinates of all boxes
	 * This is generated from {@link #boxmap} by {@link #calculateMaps()}. */
	public Pos[] boxes; // derived from boxmap

	/** A map of the tiles where targets are placed, allowing for faster lookups.
	 * This is generated from {@link #targets} by {@link #calculateMaps()}. */
	public boolean[][] targetmap = null; // derived from targets

	/** A map of the tiles the player can reach without moving boxes.
	 * This is generated by {@link #calculateMaps()}
	 * from {@link #floor} and {@link #boxmap}*/
	public boolean[][] reachable = null; // derived from floor, boxes and player
	
	public Board(int width, int height, int boxCount) {
		if (width > 125 || height > 125 || boxCount > 125) throw new RuntimeException("Too large board or too many boxes");
		
		this.floor = new boolean[width][height];
		this.boxmap = new boolean[width][height];
		this.targets = new Pos[boxCount];
	}
	
	/**
	 * Calculates and sets the box and reachable tile maps. 
	 */
	public void calculateMaps() {	
		if (targetmap == null) {
			targetmap = new boolean[floor.length][floor[0].length]; // auto-initializes to false
			for (Pos p : targets) {
				targetmap[p.x][p.y] = true;
			}		
		}

		if (safeTiles == null) {
			calcSafeTiles();
		}
			
		boxes = new Pos[targets.length];
		int storeBoxAt = 0;
		for (byte x = 0; x < boxmap.length; x++) {
			for (byte y = 0; y < boxmap[0].length; y++) {
				if (boxmap[x][y]) {
					boxes[storeBoxAt++] = new Pos(x,y);
				}
			}
		}
		assert(storeBoxAt == boxes.length);
		

		reachable = new boolean[floor.length][floor[0].length]; // auto-initializes to false
		addReachable(player.x, player.y);
	}
	
	/**
	 * Calculates the safe tile map. Requires target map!
	 */
	private void calcSafeTiles() {
		safeTiles = new boolean[floor.length][floor[0].length]; // auto-initializes to false
		for (byte x = 0; x < floor.length; x++) {
			for (byte y = 0; y < floor[0].length; y++) {
				if (floor[x][y]) { // if its not floor, we cannot push anything there
					if (targetmap[x][y]) {
						safeTiles[x][y] = true;
						continue;
					}
					try {
						if ( ((!floor[x][y-1]) || (!floor[x][y+1])) &&
								((!floor[x-1][y]) || (!floor[x+1][y])) ) {
							// both a horizontal and a vertical neighbour are walls
							continue; // --> corner -> not safe, leave at false
						}
					} catch (ArrayIndexOutOfBoundsException e) {
						// on correct fields, tiles on the edge of the board
						// are either walls or outside the reachable area.
						continue;
					}
					
					safeTiles[x][y] = true; // TODO better rules, fallback for now
				}
			}
		}
	}

	/**
	 * Checks if the given coordinate can be stepped on. If yes, it
	 *   a) marks it as reachable and 
	 *   b) performs the check for its four direct neighbors.
	 * This allows to "flood fill" the reachable area.
	 * @param x the x coordinate of the tile to check (and maybe add) as reachable
	 * @param y the y coordinate of the tile to check (and maybe add) as reachable
	 */
	private void addReachable(int x, int y) {
		try { // DEBUG
			if (!reachable[x][y] && floor[x][y] && !boxmap[x][y]) {
				reachable[x][y] = true;
				addReachable(x-1,y);
				addReachable(x+1,y);
				addReachable(x,y-1);
				addReachable(x,y+1);
			}
		}
		catch (ArrayIndexOutOfBoundsException e) {
			throw new RuntimeException("addReachable ran off world. board probably not surrounded by walls.");
		}
	}
	
	/**
	 * Tests if a move is possible. Maps have to be calculated before calling this method.
	 * A move is possible if:
	 *   a) the player can reach the direction from which the box will be pushed
	 *   b) the target field is a floor tile
	 *   c) the target field is not occupied by a box
	 * @param boxID the ID of the box to be moved
	 * @param direction the direction in which the box is to be moved (1: up, 2: right, 3: down, 4: left)
	 * @return true if the move is possible
	 */
	public boolean canMove(Pos box, int direction) {
		int xdir = 0, ydir = 0;
		switch (direction) {
		case 1: xdir = 0; ydir = -1; break;
		case 2: xdir = 1; ydir = 0; break;
		case 3: xdir = 0; ydir = 1; break;
		case 4: xdir = -1; ydir = 0; break;
		default: throw new RuntimeException("Invalid direction " + direction);
		}
		
		return reachable[box.x - xdir][box.y - ydir] && // can get to pushing pos
				safeTiles[box.x+xdir][box.y+ydir] && // there is a acceptable place to push to
				!boxmap[box.x+xdir][box.y+ydir]; // and it is free
	}
	
	public List<Move> getPossibleMoves() {
		List<Move> result = new LinkedList<Move>();
		for (int box = 0; box < boxes.length; box++) {
			for (int dir = 1; dir < 5; dir++) {
				if ( canMove(boxes[box],dir) ) result.add(new Move(boxes[box],dir));
			}
		}
		//Collections.shuffle(result);
		return result;
	}
	
	/**
	 * Performs a move, changing the board. Does NOT check for invalid moves!
	 * 
	 * Maps do NOT have to be calculated before calling this method,
	 * maps that have been calculated are discarded!
	 * 
	 * This allows fast application of moves.
	 * 
	 * @see {@link #move(List)}
	 * 
	 * @param boxID the ID of the box to be moved
	 * @param direction the direction in which the box is to be moved (1: up, 2: right, 3: down, 4: left)
	 */
	public void move(Pos box, int direction) {
		int xdir = 0, ydir = 0;
		switch (direction) {
		case 1: xdir = 0; ydir = -1; break;
		case 2: xdir = 1; ydir = 0; break;
		case 3: xdir = 0; ydir = 1; break;
		case 4: xdir = -1; ydir = 0; break;
		default: throw new RuntimeException("Invalid direction " + direction);
		}
		
		player = box.clone(); // place player at the position resulting from the push
		boxmap[box.x][box.y] = false;
		boxmap[box.x+xdir][box.y+ydir] = true;
		
		// maps are invalid now, discard
		reachable = null;
		boxes = null;
	}
	
	/**
	 * Performs a list of moves, changing the board. Does NOT check for invalid moves!
	 * 
	 * Maps do NOT have to be calculated before calling this method,
	 * maps that have been calculated are discarded!
	 * 
	 * This allows fast application of many moves.
	 * 
	 * @param moveList
	 * @see {@link #move(int, int)}
	 */
	public void move(List<Move> moveList) {
		for (Move m : moveList) {
			move(m.box, m.direction);
		}
	}
	
	/**
	 * Creates an independent copy of this board, without the maps.
	 * Things that are not meant to change (floor, targets, safe tiles, ...) are shared references!
	 * @return the copy
	 */
	public Board partialClone() {
		Board result = new Board(floor.length, floor[0].length,targets.length);
		
		
		result.floor = floor;
		result.safeTiles = safeTiles;
		
		result.targets = targets;
		result.player = player.clone();

		for (int x = 0; x < boxmap.length; x++) {
			result.boxmap[x] = boxmap[x].clone();
		}

		result.targetmap = targetmap;

		return result;
	}

	/**
	 * @return The sum of the ("city-block") distances between each box and the nearest target.
	 * Does require maps (for now!).
	 */
	public int distanceSum() {
		int result = 0;
		for (Pos box : boxes) {
			int mindist = Integer.MAX_VALUE;
			for (Pos target : targets) {
				int dist = box.distance(target);
				if (dist < mindist) {
					mindist = dist;
				}
			}
			result += mindist;
		}
		return result;
	}
	
	/**
	 * Checks if the board is solved. Assumes that board is valid, i.e. no invalid moves have been made!
	 * Requires maps until distanceSum is fixed.
	 * @return true if the board is solved
	 */
	public boolean isSolved() {
		return distanceSum() == 0;
	}
		
	/**
	 * Checks if the board is deadlocked (i.e. cannot be won).
	 * Requires maps.
	 * @return true if the board is deadlocked
	 */
	public boolean isDeadlocked() {
		Board workBoard = this.partialClone();
		
		boolean hasRemoved = true;
		while (hasRemoved) {
			hasRemoved = false;
			workBoard.calculateMaps();
			for (Pos box : workBoard.boxes) {
				if (box == null) break; // end of boxes
				if (workBoard.canMove(box, 1) || workBoard.canMove(box, 2) ||
						workBoard.canMove(box, 3) || workBoard.canMove(box, 4) ) {
					// box can move -> remove it
					hasRemoved = true;
					workBoard.boxmap[box.x][box.y] = false;
					//break; // break the for loop
				}
			}
		}
		
		for (Pos box : workBoard.boxes) {
			if (box == null) break; // end of boxes
			if (!workBoard.targetmap[box.x][box.y]) // ignore boxes on targets
				return true; // at least one box could not be moved after removing movable ones
		}
		
		return false;
	}

	/**
	 * Helper function for debugging. Prints a map.
	 * @param map The map to be printed
	 * @param fg The character to be used for foreground (true) tiles.
	 * @param bg The character to be used for background (false) tiles.
	 */
	public static void printMap(boolean[][] map, char fg, char bg) {
		for (int y = 0; y < map[0].length; y++) {
			for (int x = 0; x < map[0].length; x++) {
				System.out.print(map[x][y] ? fg : bg);
			}
			System.out.println();
		}		
	}
	
	/**
	 * Converts the board to a multi-line string showing its current state.
	 * Maps will be calculated automatically if not already available.
	 */
	public String toString() {
		if (targetmap == null) calculateMaps();
		
		StringBuffer result = new StringBuffer();
		for (int y = 0; y < floor[0].length; y++) {
			for (int x = 0; x < floor.length; x++) {
				if (!floor[x][y]) {
					result.append("#");
					continue;
				}
				if (boxmap[x][y]) {
					if (targetmap[x][y]) {
						result.append("*");
					} else {
						result.append("$");
					}
					continue;
				}
				if (x == player.x && y == player.y) {
					if (targetmap[x][y]) {
						result.append("+");
					} else {
						result.append("@");
					}
					continue;					
				}
				// if none of the above, either target or floor
				if (targetmap[x][y]) {
					result.append(".");
				} else {
					result.append(" ");
				}
				
			}
			result.append("\n");
		}
		return result.toString();
	}
	
}
